853. Sereja and Array

Sereja has got an array, consisting of n integers a₁, a₂, ..., a_n. Sereja is an active boy, so he is now going to complete m operations. Each operation will have one of the three forms:

· Make v_i-th array element equal to x_i. In other words, perform the assignment a_vi = x_i.

· Increase each array element by y_i. In other words, perform n assignments a_i  = a_i +  y_i (1 ≤ i ≤ n).

· Take a piece of paper and write out the q_i-th array element. That is, the element a_qi.

Help Sereja, complete all his operations.

Input. The first line contains integers n, m (1 ≤ n, m ≤ 10⁵). The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) – the original array.

Next m lines describe operations, the i-th line describes the i-th operation. The first number in the i-th line is integer t_i (1 ≤  t_i  ≤ 3), that represents the operation type.

· If t_i  = 1, then it is followed by two integers v_i and x_i (1 ≤  v_i  ≤ n, 1 ≤  x_i  ≤ 10⁹).

· If t_i  = 2, then it is followed by integer y_i (1 ≤  y_i  ≤ 10⁴).

· If t_i  = 3, then it is followed by integer q_i (1 ≤  q_i ≤ n).

Output. For each third type operation print value a_qi. Print the values in the order, in which the corresponding queries follow in the input.

Sample input 1	Sample output 1
5 6 1 2 3 4 5 3 1 2 10 1 1 5 3 1 2 10 3 1	1 5 15
Sample input 2	Sample output 2
10 11 1 2 3 4 5 6 7 8 9 10 3 2 3 9 2 10 3 1 3 10 1 1 10 2 10 2 10 3 1 3 10 3 9	2 9 11 20 30 40 39

SOLUTION

array processing

Algorithm analysis

Read the input array a. Create a variable add, initialize it to zero. When performing an operation of the second type (increasing each element of the array by y_i), add add + = y_i. Thus, in the absence of operations of the first type (assignments a_vi = x_i), the final state of the element a_i will be equal to the initial state of a_i plus add. Then, to preserve the last property in the case of the first operation, we must assign a_vi = x_i – add.

Example

Let’s look at the first example. Let a_i be the state of the array in memory, a_i’ be the real state of the array. Initial state of the array:

Since a_i’ = a_i + add, but initially add = 0, then a_i’ = a_i. That is, initially physically each element of the array equals to itself.

Add 10 to all the numbers in the array, add = add + 10 = 10. The following relation holds: a_i’ = a_i + add.

The next query: a₁’ = 5. Physically you should make the assignment

a₁ = 5 – add,

after which the array will take the form:

Next query is to print the first element. We get a₁’ = a₁ + add = -5 + 10 = 5.

Again add 10 to all the numbers of array: add = add + 10 = 20.

First element equals to a₁’ = a₁ + add = -5 + 20 = 15.

Algorithm realization

Declare an array a.

#define MAX 100010

int a[MAX];

Read the input array.

scanf("%d %d",&n,&m);

for(i = 1; i <= n; i++)

scanf("%d",&a[i]);

Initialize the variable add.

add = 0;

Process m operations sequentially. The type of operation read into the variable t.

for(i = 0; i < m; i++)

{

scanf("%d",&t);

Carry out the assignment a_vi = x_i

if (t == 1)

{

scanf("%d %d",&v,&x);

a[v] = x - add;

} else

Increase each element of array by y_i.

if (t == 2)

{

scanf("%d",&y);

add += y;

} else

Print the q_i-th element of the array.

{

scanf("%d",&q);

printf("%d\n",a[q] + add);

}

}